\chapter{Algoritmo de generación de terapias}

\section{Introducción}
En este capitulo se hace una descripción detallada del algoritmo de generación de terapias, tanto de su parte constante como sus partes variables. Primero se explica la parte invarible del algoritmo, luego las partes variables de este y las distintas alternativas provistas por el SDK y finalmente se hace una breve introducción a la selección de la política de generación a través del plugin.

La elección de la política se hace a través del plugin y se proveen un conjunto de políticas convencionales por medio del SDK (Software Developement Kit).
El objetivo es permitirle al usuario (implementador plugin) adaptar la generación de terapias a sus requerimientos.

\section{Algoritmo de Generación (parte invariable)}
Basándose en la necesidad de un algoritmo altamente parametrizable que pueda modificar su comportamiento de una forma sencilla, sin violar OCP. Se uso el patrón $Template method$ para separar el algoritmo en dos partes una parte fija (invariable) y una parte variable. Para implementarlo se desarrollaron los conceptos de algoritmo de generación para terapias (parte fija) y políticas de generación (parte variable). implementó la idea de algoritmo genérico y políticas de generación donde el sistema provee un algoritmo, que en etapas determinadas, consulta a una política cual es el siguiente paso a seguir.\\


\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
void generate_therapies(init_sequence)
{
    root = create_node(init_sequence)
    process_node(root)
}
\end{lstlisting}


El algoritmo toma la secuencia inicial introducida por el usuario, crea un nodo y llama a una sub rutina recursiva $process\_node$. Esta tiene la función de procesar el nodo para generar el siguiente nivel de mutantes.\\

\begin{flushleft}
\begin{minipage}{\linewidth}
\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
Score process_node(node)
{
    valid_antivirals = select_antivirals(get_sequence(node))

    if (valid_antivirals is not empty)
    {
	    combine(valid_antivirals)
   		post_combinations_callback(process_node)
    }
    delete node
    return score
}
\end{lstlisting}
\end{minipage}
\end{flushleft}

Funcionamiento: toma un nodo del árbol, determina el conjunto de los antirretrovirales que son efectivos contra esa secuencia (mutante). Si el conjunto de antirretrovirales aplicables no es vació se generan todas las combinaciones según el Algoritmo Combinatorio (Explicado en detalle en el capítulo 8). Una vez generadas las combinaciones se pregunta a la política a través del método $post\_combination\_callback$ que hacer con los nodos generados en la etapa de combinación. Finalmente, al terminar de procesar el nodo se lo elimina y se retorna su puntaje.

Esta sub rutina es llamada por el algoritmo combinatorio cada vez que una combinación de antirretrovirales genera una nueva mutante.\\

\begin{flushleft}
\begin{minipage}{\linewidth}
\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
void update(mutant)
{
	node = create_node(mutant)
	therapy_status = continue_therapy(node)
	
	case(therapy_status)
    {
   		Last :
        	add_child(parent, node)
        	therapy = get_therapy(node)
           	ranker(therapy)
           	delete node

   		Continue :
           	add_child(parent,node)
           	therapy = get_therapy(node)
            ranker(therapy)

			you_must = node_creation_callback(node)
            if (you_must == ProcessChild)
            	process_node(node)

   		Discard :
        	delete node
   	}
}
\end{lstlisting}
\end{minipage}
\end{flushleft}


Funcionamiento: toma una nueva mutante, genera un nodo a partir de esta y pregunta que debe hacer con la futura terapia parcial.


\begin{itemize}
\item Last (someterla al ranking y descartarla): Agrega el nodo a la terapia, la coloca en el ranking y elimina el nodo.
\item Continue (continuarla): Agrega el nodo a la terapia, la coloca en el ranking, a través de la política decide que hacer con el nodo generado $node\_creation\_callback$.
	\begin{itemize}
	\item ProcessChild (procesarlo): llama a $process\_node$.
	\item ContinueWithSibling (continuar con el siguiente): continua con la siguiente secuencia y deja este sin procesar.
	\end{itemize}
\item Discard (descartarla): elimina el nodo.
\end{itemize}


Vale la pena notar las etapas del calculo, en la que una política iba a influenciar el algoritmo de generación. Se identificaron dos etapas que permiten hacer el algoritmo versátil:

\begin{itemize}
\item Después de generar un nodo $node\_creation\_callback$, dando la posibilidad de procesarlo o continuar con el siguiente. 
\item Después de generar todos los nodos hijos $post\_combinations\_callback$, de esta forma la política pueda indicarle al algoritmo que hacer con los nodos que le quedaron pendientes de procesar (ContinueWithSibling).
\end{itemize}   

\section{Políticas de Generación (parte variable)}
La idea detrás de las políticas es disminuir el acoplamiento entre el sistema y el plugin tanto como sea posible. Una política es un objeto simple que mediante un conjunto de mensajes pre establecidos indica al algoritmo genérico que hacer en partes determinadas del calculo. Para esto las políticas implementan la interfaz $GenerationPolicy$ que consta de dos primitivas:
\begin{itemize}
\item $node\_creation\_callback$: indica que hacer con un nodo una vez generado.
\item $post\_combinations\_callback$: indica que hacer luego de generar todos los nodos hijos del nodo actual.
\end{itemize}

\subsection{Las Políticas Provistas}
A continuación daremos una descripción de las políticas provistos en el SDK junto con las ventajas y desventajas de cada uno. Notar que son algoritmos de búsqueda sobre árboles y que fueron adaptados para usarlos como algoritmos de generación.


\subsubsection{B.F.S (Breadth First search)}
Este clásico algoritmo comienza con el nodo raíz y explora todos los nodos vecinos. Luego cada uno de estos, exploran sus nodos vecinos, y así sucesivamente, hasta explorar todos los nodos. \\

\begin{figure}
\centering
\includegraphics[scale=0.6]{pictures/BFS.jpeg}	  	
\caption{Ejemplo de orden en que se generan los nodos para BFS.} 
\end{figure}

Para hacer que el algoritmo genérico se comporte como BFS los callback se implementaron así:

\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
CallbackAction node_creation_callback(node)
{
    insert_into(pending, node)
    return ContinueWithSibling
}
\end{lstlisting}

Se guarda el nodo en la lista de pendientes y se retorna $ContinueWithSibling$ para indicar que se debe procesar el siguiente.

\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
void post_combinations_callback(processor)
{
    for all node in pending do
    {
        processor(node)
    }
}
\end{lstlisting}

Después de realizar las combinaciones se procesan todos los nodos de la lista de pendientes.

\subsubsection{D.F.S (Depth First Search)}
Otro clásico algoritmo, en este caso se comienza con el nodo raíz y explora, tan lejos como pueda, a lo largo de cada rama antes de retroceder.
Dado que el algoritmo llega al final de una rama de forma mas rápida, se podrán obtener las terapias de manera más rápida gracias al diseño basado en observadores.\\


\begin{figure}
\centering
\includegraphics[scale=0.6]{pictures/DFS.jpeg}	  	
\caption{Ejemplo de orden en que se generan los nodos para DFS.} 
\end{figure}

Para hacer que el algoritmo genérico se comporte como DFS los callback se implementaron así:

\begin{lstlisting}[language=C++, numbers=left, numberstyle=\tiny, tabsize=4,fontadjust=true,frame=trBL,basicstyle=\tt, tabsize=4]
CallbackAction node_creation_callback(node)
{
    return ProcessChild
}

virtual void post_combinations_callback(processor)
{}
\end{lstlisting}

Notar que cada vez que genero un nodo lo proceso inmediatamente, por lo que luego realizar las combinaciones no hay nodos que procesar.

\subsubsection{Better Beam} 
Es un caso particular del algoritmo Best First Search el cual recorre un árbol pero teniendo en cuenta un criterio, en este caso la decisión de tomar los $N$ mejores nodos. Cuando nos referimos a \"mejores\", nos referimos a aquellos con puntaje más alto según la función de scoring provista por el plugin. Este enfoque reduce el tiempo de computo notablemente.\\

La implementación es similar a la BFS, solo que en lugar de guardar los nodos en un repositorio común ($pending$), se los guarda en un objeto $Ranker$ que solo conserva los $N$ mejores.

\section{Especificando la Política al Plugin}
Como se aclaro anteriormente, el plugin es quien da al sistema la política a usar, lo cual da al implementador de plugin la posibilidad de definir su propia política de generación. Esto se logra proveyendo en la interfaz $plugin$ el método $generation\_policy()$ que provee al sistema de un objeto política. 
Dentro de este método el implementador puede optar por retornar su propia política o optar por una de las políticas pre diseñada: 

\begin{itemize}
\item $BetterBeam(N)$, donde $N$ es un entero mayor a 1.
\item $Depth$ recorrido en profundidad.
\item $Breadth$ recorrido en ancho.
\end{itemize}








